DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2023.19

Finding Degree-Constrained Acyclic Orientations

Authors: Jaroslav Garvardt, Malte Renken, Jannik Schestag, and Mathias Weller

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract

We consider the problem of orienting a given, undirected graph into a (directed) acyclic graph such that the in-degree of each vertex v is in a prescribed list λ(v). Variants of this problem have been studied for a long time and with various applications, but mostly without the requirement for acyclicity. Without this requirement, the problem is closely related to the classical General Factor problem, which is known to be NP-hard in general, but polynomial-time solvable if no list λ(v) contains large "gaps" [Cornuéjols, J. Comb. Theory B, 1988]. In contrast, we show that deciding if an acyclic orientation exists is NP-hard even in the absence of such "gaps". On the positive side, we design parameterized algorithms for various, natural parameterizations of the acyclic orientation problem. A special case of the orientation problem with degree constraints recently came up in the context of reconstructing evolutionary histories (that is, phylogenetic networks). This phylogenetic setting imposes additional structure onto the problem that can be exploited algorithmically, allowing us to show fixed-parameter tractability when parameterized by either the treewidth of G (a smaller parameter than the frequently employed "level"), by the number of vertices v for which |λ(v)| ≥ 2, by the number of vertices v for which the highest value in λ(v) is at least 2. While the latter result can be extended to the general degree-constraint acyclic orientation problem, we show that the former cannot unless FPT=W[1].

Cite as

Jaroslav Garvardt, Malte Renken, Jannik Schestag, and Mathias Weller. Finding Degree-Constrained Acyclic Orientations. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{garvardt_et_al:LIPIcs.IPEC.2023.19,
  author =	{Garvardt, Jaroslav and Renken, Malte and Schestag, Jannik and Weller, Mathias},
  title =	{{Finding Degree-Constrained Acyclic Orientations}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.19},
  URN =		{urn:nbn:de:0030-drops-194383},
  doi =		{10.4230/LIPIcs.IPEC.2023.19},
  annote =	{Keywords: Graph Orientation, Phylogenetic Networks, General Factor, NP-hardness, Parameterized Algorithms, Treewidth}
}

Document

DOI: 10.4230/LIPIcs.IPEC.2023.20

Graph Clustering Problems Under the Lens of Parameterized Local Search

Authors: Jaroslav Garvardt, Nils Morawietz, André Nichterlein, and Mathias Weller

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract

Cluster Editing is the problem of finding the minimum number of edge-modifications that transform a given graph G into a cluster graph G', that is, each connected component of G' is a clique. Similarly, in the Cluster Deletion problem, we further restrict the sought cluster graph G' to contain only edges that are also present in G. In this work, we consider the parameterized complexity of a local search variant for both problems: LS Cluster Deletion and LS Cluster Editing. Herein, the input also comprises an integer k and a partition 𝒞 of the vertex set of G that describes an initial cluster graph G^*, and we are to decide whether the "k-move-neighborhood" of G^* contains a cluster graph G' that is "better" (uses less modifications) than G^*. Roughly speaking, two cluster graphs G₁ and G₂ are k-move-neighbors if G₁ can be obtained from G₂ by moving at most k vertices to different connected components. We consider parameterizations by k + 𝓁 for some natural parameters 𝓁, such as the number of clusters in 𝒞, the size of a largest cluster in 𝒞, or the cluster-vertex-deletion number (cvd) of G. Our main lower-bound results are that LS Cluster Editing is W[1]-hard when parameterized by k even if 𝒞 has size two and that both LS Cluster Deletion and LS Cluster Editing are W[1]-hard when parameterized by k + 𝓁, where 𝓁 is the size of the largest cluster of 𝒞. On the positive side, we show that both problems admit an algorithm that runs in k^{𝒪(k)}⋅ cvd^{3k} ⋅ n^{𝒪(1)} time and either finds a better cluster graph or correctly outputs that there is no better cluster graph in the k-move-neighborhood of the initial cluster graph. As an intermediate result, we also obtain an algorithm that solves Cluster Deletion in cvd^{cvd} ⋅ n^{𝒪(1)} time.

Cite as

Jaroslav Garvardt, Nils Morawietz, André Nichterlein, and Mathias Weller. Graph Clustering Problems Under the Lens of Parameterized Local Search. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{garvardt_et_al:LIPIcs.IPEC.2023.20,
  author =	{Garvardt, Jaroslav and Morawietz, Nils and Nichterlein, Andr\'{e} and Weller, Mathias},
  title =	{{Graph Clustering Problems Under the Lens of Parameterized Local Search}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{20:1--20:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.20},
  URN =		{urn:nbn:de:0030-drops-194391},
  doi =		{10.4230/LIPIcs.IPEC.2023.20},
  annote =	{Keywords: parameterized local search, permissive local search, FPT, W\lbrack1\rbrack-hardness}
}

Search Results

Documents authored by Garvardt, Jaroslav

Finding Degree-Constrained Acyclic Orientations

Abstract

Cite as

Graph Clustering Problems Under the Lens of Parameterized Local Search

Abstract

Cite as

Thanks for your feedback!

Could not send message